Radio identification is a technique used for storing and recovering data remotely by using markers known as radio tags, or “RFID tags”. A radio tag is a small item such as a sticky label that can be stuck on or incorporated in entities or goods. It comprises an antenna associated with an electronic chip that enables it to receive and respond to radio requests transmitted from a transceiver referred to as a “reader”. By way of example, radio tags are used for identifying people when the tags are incorporated in passports, in tickets, or in payment cards, or for identifying goods as with a bar code. This application to goods facilitates managing stock and makes it possible to track stock throughout the distribution system for the goods. Nowadays numerous sectors of activity, such as the pharmaceutical industry, distribution, fashion, and book selling make use of RFID systems for tracking articles. RFID technology is being used increasingly to automate manual processes, to authenticate and protect freight, and to provide real time visibility of stocks.
Among existing mechanisms for identifying a radio tag, the electronic product code (EPC) consortium EPCglobal has standardized a tag identification protocol commonly known as the “tag singulation” mechanism [EPCglobal: EPC Radio-frequency identity protocols, class-1 generation-2 UHF RFID, Protocol for communications at 860-960 MHz, Version 1.2.0]. The identification mechanism is adapted to managing collisions at radio level when a plurality of radio tags respond simultaneously to a request from a reader. It thus enables a radio reader to identify, from among a set of tags, each tag in succession in order subsequently to converse with one identified tag at a time in the context of some specific application. By way of example, such an application is an authentication application adapted to verifying that the identified tag is indeed the tag that it holds itself out to be. Thus, associating these identification and authentication mechanisms makes it possible to provide accurate tracking of goods provided with such radio tags, and to combat counterfeiting effectively by acting at each step in a system for distributing goods to verify the authenticity and thus the origin of the goods.
The identification protocol defined by the EPCglobal consortium is described with reference to FIG. 1.
In a prior stage (not shown), a radio reader R decides on a class of tag to be interrogated. By way of example, this may be all tags coming from a given manufacturer. It is assumed that a plurality of tags T1, . . . , Tn satisfying this criterion are within radio range of a radio reader R.
In a first parameter-setting step E10, the reader R sets a value for a parameter written q that determines a range of time slots during which the tags in radio range of the reader are to be interrogated by the reader R. The number of time slots in the range is equal to 2q.
In a query step E11, the reader R transmits a query message QUERY over the radio channel, which message contains the number of time slots as determined beforehand, specifically 2q. In a selection step E12 performed after the reader R has transmitted the query message, the tags T1, . . . , Tn in radio range of the reader R select respective time slots within the proposed range. Thus, the time slot selected by each tag is a number lying in the range 0 to 2q−1. This time slot is selected by each tag in random manner and it determines a particular time interval during which the tag is capable of replying to the reader, and possibly of being isolated by the reader R during the identification protocol in order to dialog in privileged manner with the reader in the context of a particular application, e.g. an authentication application.
A tag interrogated during a time slot that it has selected replies to the reader R by sending a 16-bit random value RN selected by the tag. The slot 0 is representative of the first slot associated with the query message QUERY sent by the reader R during step E11. It is assumed here that only the tag Tj has selected 0 as its time slot. The tag Tj is thus concerned by the query message QUERY received from the reader. The tag Tj then acts in a reply step E13 to send a reply message REP to the reader R, which message includes a random value RN selected by the tag Tj.
In a test step E14, the reader R determines whether zero, one, or a plurality of tags have replied to the query message QUERY that it sent.
As specified above, it is assumed at this point that only the tag Tj has replied. In a reply step E15, the reader R replies to the tag Tj by sending an acknowledgment message ACK that includes the random value RN received from the tag Tj. Thus, the tag Tj knows that the reader R has received its reply message correctly.
In an identification step E16, the tag Tj sends an identification message ID to the reader R, which message includes an information sequence specific to the tag Tj. This sequence comprises a 16-bit character string known as its product code (PC) that identifies the capabilities of the tag, an electronic product code (EPC) on 64 to 128 bits that identifies the tag Tj in unique manner, and a 16-bit cyclic redundancy code (CRC) for correcting errors, which CRC is determined on the basis of the code PC and the identifier EPC and serves to detect transmission errors.
In a second situation (not shown in FIG. 1) in which a plurality of tags reply to the query message QUERY sent by the reader R in step E11, the tags that have replied put themselves into a temporary waiting state, also known as a “hibernation” state. This situation corresponds to a collision between replies from tags that therefore cannot be processed by the reader R. The reader R sends a new query message, conventionally written QUERYREP, which message contains a following time slot. In a third situation (not shown in FIG. 1), in which no tag has replied to the query message QUERY, the reader R sends a new query message QUERYREP that includes the following time slot.
Once all of the time slots in the range [0, 2q−1] have been processed, the reader can transmit the query message QUERY once again in order to attempt to identify the tags that could not be identified while sending earlier query messages QUERY and QUERYREP.
At the end of identification step E16, all of the other tags T1, . . . , Tj−1, Tj+1, . . . , Tn are in a waiting state, either because they have entered into a hibernation state, or because they are not concerned by the current exchange. The reader R can then dialog with the tag Tj that it has identified, in a manner that depends on the particular needs of an application. One such dialog is shown diagrammatically in FIG. 1 by a step E17 that is dedicated to an application. In the context of an embodiment of the present invention, an advantageous example is an authentication application that enables the reader R to ensure that the tag Tj that has identified itself with the reader is indeed the tag that it holds itself out to be. It should be observed that such authentication takes place after the tag has identified itself during the above-described identification protocol.
There are several schemes in existence for authenticating a tag with a radio reader. For example a known authentication scheme is named “GPS” or “cryptoGPS” for its inventors Girault, Palliès, Poupard, and Stern [M. Girault, G. Poupard, and J. Stern “On the fly authentication and signature schemes based on groups of unknown order”, Journal of Cryptology, pp. 463-488, Vol. 19, No. 4, 2006]. The GPS scheme is a public key authentication technique. It is a protocol of the “zero knowledge” type in which security relies on the difficulty of computing the discrete logarithm in a group. By way of example, implementation of this scheme may rely on cryptography based on elliptic curves.
This scheme is commonly used so that a device having very little power in terms of memory and/or computation power can authenticate itself with a second device having greater power. The protocol is such that the cost of authentication for the less-powerful device can usually be reduced by means of a series of optimizations. For example, one optimization of the GPS scheme relies on a so-called “coupon” mode. That mode consists in acting before an authentication session to calculate everything that can be calculated beforehand, so as to leave a minimum of operations that need to be performed while the authentication proper is taking place. This makes the GPS protocol very well adapted to applications based on RFID tags.
With reference to FIG. 2, there follows a description of an example of an implementation of a GPS authentication scheme for authenticating a radio tag with a reader and as used in the prior art. The example described here is based on elliptic curves; it uses a subgroup of points generated by a point P on a curve E. The implementation described here makes use of tag authentication coupons and of regenerating random numbers associated with each of those coupons by the tag, thus constituting an optimization in a basic GPS scheme. In this implementation, the arithmetic calculations on the elliptic curves are performed by the reader, and only basic arithmetic operations are executed by the tag. It can be understood that that example is most advantageous in terms of performance and implementation space for the tag.
In that scheme, an authentication system has at least one tag T adapted to authenticate itself with a reader R when the tag comes within the proximity of the reader R.
In conventional manner, the scheme comprises two stages: a configuration stage E20 during which the authentication data is calculated and/or supplied to the tag T and to the reader R, and an authentication stage E21 during which the tag T authenticates itself with the reader R. The configuration stage E20 need be performed only once in the lifetime of the system. The authentication stage E21 is executed each time the tag is authenticated with the reader R.
During the configuration stage E20, a pair of GPS keys (s, V) is generated. The pair comprises a secret key s and an associated public key V. The secret key s, specific to the tag T, is stored in the tag T and is never extracted or transmitted from the tag T. The public key V is accessible to the reader R. The keys s and V are linked, e.g. by means of the following formula: V=−sP, where P is a point on the elliptic curve E known to the reader R. In a variant, V=sP. In other words, the public key V is calculated by addition on the elliptic curve by adding the point P s times. In the presently-described implementation of the GPS scheme, sometimes known as the “reduced coupon” mode, a second secret key k, known as a regeneration key, is installed in the tag T. It is used as a parameter for a pseudo-random function (PRF) installed in the tag T.
During the configuration stage E20, in a configuration step E20-1, a predetermined number n of values are recalculated, which values are commonly referred to as authentication coupons of the tag and written xi, 1≦i≦n. The coupon of index i is written xi. The index i is an identification index of the coupon xi. In order to calculate the coupon xi, a random number ri is generated by means of the pseudo-random function PRF using the regeneration key k as the parameter and applied to the index i (ri=PRFk(i)). The random numbers ri (i.e. as output from the function PRF) are of large size, e.g. 1100 bits. The authentication coupon xi of the tag is then calculated using the following formula: xi=HASH(riP), where HASH is a known hashing function applied to adding the point P on the elliptic curve ri times. This addition, and to a lesser extent the evaluation of the hashing function HASH, are operations that are expensive in terms of calculation power. It is thus common practice for the coupons xi to be precalculated by a calculation entity (not shown) of the authentication system that is different from the tag T and from the reader R. The authentication coupons xi of the tag are then stored in the tag T in a memory (not shown) of the tag T for use during authentications with the reader R.
During the authentication stage E21, in an initial selection-and-sending step E21-1, the tag T that is authenticating itself selects a coupon xi of index i. At the end of step E21-1, the selected coupon xi is sent to the reader R.
In a step 21-2 of selecting and sending a challenge, the reader R generates a challenge c. The challenge c is generated randomly. At the end of step E21-2, the challenge c is sent by the reader R to the tag T.
In a regeneration and calculation step 21-3, the tag T regenerates the random number ri. For this purpose, the pseudo-random function PRF installed in the tag T and parameterized by the secret regeneration key k is applied to the index i that identifies the coupon xi. It is known that the pseudo-random function requires little calculation power from the tag T. The tag T then calculates a reply y to the challenge c using the following formula: y=ri+sc. The reply y is the sum of the random number ri and the scalar product of the secret key s and of the challenge c. At the end of the step E21-3, the reply y is sent to the reader R.
In a verification step E21-4, the reader R verifies that the coupon xi received from the tag at the end of step E21-1 is equal to a value obtained by applying the hashing function HASH to addition on the elliptic curve of the point P y times, and to addition of the public key V c times, in other words: HASH(yP+cV).
If the verification is positive (branch “Ok” in FIG. 2), then the tag T has been correctly identified with the reader R.
By way of example, the function HASH may be the function SHA-1, where SHA stands for “secure hash algorithm”.
It may be observed that when tag authentication is implemented in accordance with the scheme described with reference to FIG. 2, this necessarily takes place after the reader has isolated a particular tag during the identification protocol described with reference to FIG. 1. Implementing the identification protocol and then the authentication protocol in succession thus requires as many messages to be exchanged as there are exchanges in both of those protocols, and as much data to be transported as needs to be exchanged between the entities involved during these two protocols.